from typing import List

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 思路是把列表从中间拆成两半，每一半都单独构建平衡树，最后合起来
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        list = self.__listNodeToList(head)
        return self.__listToBst(list)

    def __listNodeToList(self, node: ListNode) -> List:
        li = []
        n = node
        while n != None:
            li.append(n.val)
            n = n.next
        return li

    def __listToBst(self, list: List) -> TreeNode:
        length = len(list)
        if length == 0:
            return None
        if length == 1:
            return TreeNode(list[0])

        mid = length // 2
        node = TreeNode(list[mid])
        node.left = self.__listToBst(list[0:mid])
        node.right = self.__listToBst(list[mid+1:length])
        return node